A memory unit accessed by content, rather than by address or location, is called an associative memory or content addressable memory (CAM). A memory is fully-associative when any word can be held in any storage location.
When a word is to be read from a CAM, the content of the word, or part of the word, is specified. The memory locates the word which matches the specified content and marks it for reading.
FIG. 1 shows a block overview of the logical components necessary to implement a conventional CAM. Shown are address register 110, key register 112, compare array 114, and memory array 116. Such a CAM is well known in the prior art.
FIG. 2, consisting of FIGS. 2A AND 2B, shows a circuit implementing a prior art compare array like that of Block 114 in FIG. 1. Shown are a set of address lines, of which line 210 is a member, and a column of identical entries, such as entry 212. Entry 212 includes match line 0 and wordline 0.
Entry 212 also comprises a row of XOR gates and corresponding NFETs. Each XOR gate receives input from an address line and a memory element. The contents of the memory elements are set using circuitry not shown in the FIGURES. The output of each XOR gate drives an NFET whose drain is connected to a match line. Each match line is precharged by a PFET to a high state. In addition, each match line is AND'ed with a strobe to produce an output on a wordline.
XOR Gate 214, for example, receives input from address line 210 and memory element 216. Gate 214 drives NFET 218. The drain of NFET 218, in turn, is connected to match line 0. Match line 0 is precharged high by PFET 220. Match line 0 and strobe line 222 are input into AND gate 224. The output of AND gate 224 is wordline 0.
In use, the contents of address register 110 are masked by key register 112 and the resulting bits are applied to the address lines. Each match line is precharged high. Each XOR gate compares the signal on its address line with that of its memory element and drives an NFET with its output. If the XOR gate's output is high, then the NFET drives the match line low. Then, strobe 222 samples the match line of each entry in the CAM and the result is sent to memory array 116.
FIG. 3, consisting of FIGS. 3A AND 3B, shows a typical memory array bit slice of memory array 116 and identifies those elements necessary for an understanding of the prior art. As shown in FIG. 3, memory element entry 0 drives NFET 310 and the inverse of memory element 0 drives NFET 312. The drains of NFETs 310 and 312 are respectively connected to the sources of NFETs 314 and 316. NFETs 314 and 316 are driven by wordline 0. The drains of NFETs 314 and 316 are connected to bit lines 318 and 320, respectively. Bit lines 318 and 320 are precharged high by PFETs 322 and 324. The precharged bit lines are then inverted and become the true and complement outputs of the array bit slice.
In practice, a high wordline drives its associated NFETs, which, in turn, cause the true bit line to go to the inverse of the memory element and the complement bit line to go to the state of the memory element. Each bit line is then inverted, causing the output lines to reflect the state of the memory element.
The chief advantage of a CAM is that of speed. A CAM is uniquely suited to do parallel searches by data association. Moreover, the use of key register 112 allows searches on entire words or specific fields within a word. However, CAMs are generally more expensive than random access memories because each entry must have storage capability as well as logic circuits for matching. For this reason, CAMs are used in applications where the search time is very critical and must be very short, such as in a memory management unit associated with a CPU.
In prior art CAMs, the strobe had to be timed to occur after the slowest match line, otherwise the wordline might be placed in an incorrect state. However, a large time margin between the match line and the strobe subtracted from the performance of the CAM. Therefore, the timing of the strobe line was critical to CAM performance. This race condition between the match lines and the strobe added significant risk of error to the CAM design.
Therefore, there is a need in the art for a method and system of implementing a CAM which eliminates the race condition between the strobe and the match lines.